package src.DisciplesPlan.链表;

/**
 * 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

 进阶：你能尝试使用一趟扫描实现吗？

  

 示例 1：


 输入：head = [1,2,3,4,5], n = 2
 输出：[1,2,3,5]
 示例 2：

 输入：head = [1], n = 1
 输出：[]
 示例 3：

 输入：head = [1,2], n = 1
 输出：[1]
 */

public class _19删除链表的倒数第N个结点 {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 定义双指针，慢指针指向虚头，
        // 快指针先走n步，此时快慢指针同时走，当快指针指空时慢指针即为指向待删除的前一个结点
        // 定义虚头
        ListNode virNode = new ListNode(0);
        // 连接到原链表上
        virNode.next = head;
        // 快慢指针
        ListNode slow = virNode;
        ListNode fast = head;
        // 快指针先走n步
        for (int i = 0 ; i < n ; i++) {
            fast = fast.next;
        }
        // 快慢指针一起走
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return virNode.next;
    }
}
